package own.stu.jobgib.playown.alg.solution.slidingWindow;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SubString {

    public static void main(String[] args) {
        SubString s = new SubString();
        /*System.out.println(s.maxVowels("abciiidef", 3));
        System.out.println(s.maxVowels("aeiou", 2));
        System.out.println(s.maxVowels("leetcode", 3));*/

        /*System.out.println(s.longestSubstring("aaabb", 3));*/

//        System.out.println(s.removeDuplicates(new int[]{0, 0, 1, 1, 1, 1, 2, 3, 3}));
        /*System.out.println((int) 'a');
        System.out.println((int) 'A');
        System.out.println((int) 'z');
        System.out.println((int) 'Z');*/

        /*System.out.println(s.minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(s.minWindow("a", "a"));
        System.out.println(s.minWindow("a", "b"));*/

        /*System.out.println(s.maxConsecutiveAnswers("TTFF", 2));
        System.out.println(s.maxConsecutiveAnswers("TTFTTFTT", 1));*/

        System.out.println(s.lengthOfLongestSubstringTwoDistinct("eceba"));
        System.out.println(s.lengthOfLongestSubstringTwoDistinct("aaa"));
        System.out.println(s.lengthOfLongestSubstringTwoDistinct("eeffeaaaa"));
        System.out.println(s.lengthOfLongestSubstringTwoDistinct("eeffaaaa"));
        System.out.println(s.lengthOfLongestSubstringTwoDistinct("ffeeffeaaaa"));
    }

    /**
     * 76. 最小覆盖子串
     * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
     * <p>
     * 注意：
     * 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * 如果 s 中存在这样的子串，我们保证它是唯一的答案。
     * <p>
     * 示例 1：
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     * 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
     */
    public String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        int[] map = new int[128];
        int cnt = 0;
        int n = s.length();
        for (char c : t.toCharArray()) {
            if (map[c - 'A'] == 0) {
                cnt++;
            }
            map[c - 'A']++;
        }
        char c = ' ';
        int l = 0, r = 0;
        int len = 0, min = n + 1;

        for (int i = 0, j = 0; i < n; i++) {
            while (cnt > 0 && j < n) {
                c = s.charAt(j);
                map[c - 'A']--;
                if (map[c - 'A'] == 0) {
                    cnt--;
                }
                j++;
            }
            if (cnt == 0) {
                len = j - i;
                if (min > len) {
                    l = i;
                    r = j - 1;
                    min = len;
                }
                c = s.charAt(i);
                map[c - 'A']++;
                if (map[c - 'A'] == 1) {
                    cnt++;
                }
            }
        }

        return min == n + 1 ? "" : s.substring(l, r + 1);
    }

    /**
     * 1456. 定长子串中元音的最大数目
     * 给你字符串 s 和整数 k 。
     * <p>
     * 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
     * <p>
     * 英文中的 元音字母 为（a, e, i, o, u）。
     * <p>
     * 示例 3：
     * 输入：s = "leetcode", k = 3
     * 输出：2
     * 解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。
     */
    public int maxVowels(String s, int k) {
        if (s == null || s.length() == 0 || s.length() < k) {
            return 0;
        }
        char[] cs = s.toCharArray();
        int n = cs.length;
        int[] map = new int[26];
        maxVowelsInit(map, auc);

        char c = ' ';
        int sum = 0, res = 0;
        for (int i = 0; i < k; i++) {
            c = cs[i];
            sum += map[c - 'a'];
        }
        res = sum;
        if (sum == k) {
            return res;
        }

        for (int i = k; i < n; i++) {
            c = cs[i];
            char tc = cs[i - k];
            sum += map[c - 'a'] - map[tc - 'a'];
            if (sum > res) res = sum;
            if (res == k) return res;
        }
        return res;
    }

    private void maxVowelsInit(int[] map, char[] cs) {
        for (char c : cs) {
            map[c - 'a'] = 1;
        }
    }

    private static char[] auc = "aeiou".toCharArray();

    public int maxVowels_ii(String s, int k) {
        // 这个是固定窗口
        if (s == null || s.length() == 0 || s.length() < k) {
            return 0;
        }

        char[] cs = s.toCharArray();
        int n = cs.length;
        int[] map = new int[26];

        char c = ' ';
        int ans = 0;
        int cnt = 0;
        int j = 0;
        // slide window
        for (int i = 0; i < n; i++) {
            while (j < n && cnt < k) {
                c = cs[j];
                if (isAU(c)) {
                    map[c - 'a']++;
                }
                cnt++;
                j++;
            }
            if (cnt >= k) {
                ans = Math.max(ans, cal(map));
                c = cs[i];
                if (isAU(c)) {
                    map[c - 'a']--;
                }
                cnt--;
            }
        }
        return ans;
    }

    private int cal(int[] map) {
        int total = 0;
        for (Character c : au) {
            total += map[c - 'a'];
        }
        return total;
    }

    private boolean isAU(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }

    private static List<Character> au = Arrays.asList('a', 'e', 'i', 'o', 'u');

    /**
     * 395. 至少有 K 个重复字符的最长子串
     * 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。
     * <p>
     * 如果不存在这样的子字符串，则返回 0。
     * <p>
     * 示例 1：
     * 输入：s = "aaabb", k = 3
     * 输出：3
     * 解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。
     */
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0 || s.length() < k) {
            return 0;
        }

        int n = s.length();
        int[] map = new int[26];
        char c = ' ';
        /*
         这里的难点在于滑动窗口的左右滑动的控制，什么时候j停止滑动，
         因此可以不用滑动窗口
         考虑分割递归
         */
        for (int i = 0; i < n; i++) {
            c = s.charAt(i);
            map[c - 'a']++;
        }
        boolean flag = true;
        for (int i : map) {
            if (i < k && i > 0) {
                flag = false;
            }
        }
        if (flag) return s.length();

        int res = 0;
        for (int i = 0; i < n; i++) {
            c = s.charAt(i);
            /*if (map[c - 'a'] != 0 && map[c - 'a'] < k) {
                String s1 = s.substring(0, i);
                String s2 = s.substring(i + 1);
                return Math.max(longestSubstring(s1, k), longestSubstring(s2, k));
            }*/
            int cnt = map[c - 'a'];
            if (cnt < k) continue;
            int j = i;
            while (j < n && map[s.charAt(j) - 'a'] >= k) {
                j++;
            }
            res = Math.max(res, longestSubstring(s.substring(i, j), k));
            i = j;
        }

        return res;
    }

    /**
     * 80. 删除有序数组中的重复项 II
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
     * <p>
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     */
    public int removeDuplicates(int[] nums) {
        int idx = 0;
        int cnt = 2;
        for (int num : nums) {
            if (idx < cnt || nums[idx - cnt] != num) {
                nums[idx++] = num;
            }
        }
        return idx;
    }

    /**
     * 2024. 考试的最大困扰度
     * 一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。
     * <p>
     * 给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：
     * <p>
     * 每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。
     * 请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。
     * <p>
     * 输入：answerKey = "TTFF", k = 2
     * 输出：4
     * 解释：我们可以将两个 'F' 都变为 'T' ，得到 answerKey = "TTTT" 。总共有四个连续的 'T' 。
     */
    public int maxConsecutiveAnswers(String answerKey, int k) {
        if (answerKey == null || answerKey.length() == 0) {
            return 0;
        }
        int n = answerKey.length();
        if (n < k) return n;

        char[] sc = answerKey.toCharArray();
        return Math.max(maxConsecutiveAnswersHelper(sc, 'T', k),
                maxConsecutiveAnswersHelper(sc, 'F', k));
    }

    /*
     这里将原题 求 转换k次后，连续最长的 T 或者 F
     转换成了
     求不超过k的F 或者 T的最长子窜
     */
    private int maxConsecutiveAnswersHelper(char[] sc, char target, int k) {
        int n = sc.length;
        int cnt = 0;
        int max = 0;
        int i = 0, j = 0;
        while (j < n) {
            if (sc[j] == target) {
                cnt++;
            }
            while (cnt > k) {
                if (sc[i] == target) cnt--;
                i++;
            }
            max = Math.max(max, j - i + 1);
            j++;
        }
        return max;
    }

    /**
     * 928 · 最多有两个不同字符的最长子串 (lintcode)
     * 给定一个字符串，找出最长子串T的长度，它最多包含2个不同的字符。
     * <p>
     * 样例 1
     * 输入: “eceba”
     * 输出: 3
     * 解释: T 是 "ece" 它的长度是 3.
     */
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null) return 0;
        if (s.length() <= 1) return s.length();
        int n = s.length(), k = 2;
        Map<Character, Integer> map = new HashMap<>();
        int i = 0, j = 0;
        char c = ' ';
        int ans = 0;
        while (j < n) {
            if (map.size() <= k) {
                c = s.charAt(j);
                map.put(c, j);
                j++;
            }
            if (map.size() > k) {
                int min = n + 1;
                for (Integer idx : map.values()) {
                    if (min > idx) {
                        min = idx;
                    }
                }
                map.remove(s.charAt(min));
                i = min + 1;
            }
            ans = Math.max(ans, j - i);
        }
        return ans;
    }
}
